package com.zjsru.plan2024.oneday;

import java.util.ArrayList;
import java.util.List;

/**
 * 3249. 统计好节点的数目
 *
 * @Author: cookLee
 * @Date: 2024-11-14
 */
public class CountGoodNodes {

    /**
     * 主
     * \
     * 输入：edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
     * <p>
     * 输出：7
     * \
     * 输入：edges = [[0,1],[1,2],[2,3],[3,4],[0,5],[1,6],[2,7],[3,8]]
     * <p>
     * 输出：6
     * \
     *
     * @param args args
     */
    public static void main(String[] args) {
        CountGoodNodes countGoodNodes = new CountGoodNodes();
        int[][] edges = new int[][]{{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}};
        System.out.println(countGoodNodes.countGoodNodes(edges));
    }

    int ans = 0;

    List<Integer>[] list;

    /**
     * dfs
     *
     * @param edges 边缘
     * @return int
     */
    public int countGoodNodes(int[][] edges) {
        int len = edges.length + 1;
        this.list = new List[len];
        for (int i = 0; i < len; i++) {
            this.list[i] = new ArrayList<Integer>();
        }
        for (int[] edge : edges) {
            this.list[edge[0]].add(edge[1]);
            this.list[edge[1]].add(edge[0]);
        }
        this.dfs(0, -1);
        return this.ans;
    }

    /**
     * dfs
     *
     * @param node     节点
     * @param parentId 父id
     */
    private int dfs(int node, int parentId) {
        //记当前节点的所有子树大小是否一致
        boolean valid = true;
        //记录当前节点的子树总大小
        int treeSize = 0;
        //第一个子树的大小
        int subTreeSize = 0;
        for (int nextNode : this.list[node]) {
            if (nextNode != parentId) {
                int size = this.dfs(nextNode, node);
                if (subTreeSize == 0) {
                    subTreeSize = size;
                } else if (size != subTreeSize) {
                    valid = false;
                }
                treeSize += size;
            }
        }
        if (valid) {
            this.ans++;
        }
        return treeSize + 1;
    }

}
